home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7215 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.1 KB  |  66 lines
  1. Newsgroups: comp.lang.c
  2. Path: cwi.nl!dik
  3. From: dik@cwi.nl (Dik T. Winter)
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Message-ID: <DMtsB9.BBz@cwi.nl>
  6. Sender: news@cwi.nl (The Daily Dross)
  7. Nntp-Posting-Host: chrysant.cwi.nl
  8. Organization: CWI, Amsterdam
  9. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv16m$cuj@winx03.informatik.uni-wuerzburg.de>
  10. Date: Thu, 15 Feb 1996 16:25:57 GMT
  11.  
  12. In article <4fv16m$cuj@winx03.informatik.uni-wuerzburg.de> schoof@informatik.uni-wuerzburg.de (Jochen Schoof) writes:
  13.  
  14.  > in contradiction to what your function said. It is not sufficient
  15.  > to only keep track of the very last relevant digit. The problem
  16.  > mentioned above can be avoided when storing the last two relevant
  17.  > digits and I believe this technique finally is sufficient and 
  18.  > still alows to compute the digits for faculties far beyond 1000.
  19.  > Thus the following function should work as desired:
  20.  > 
  21.  > int factorial_lsd(int n)
  22.  > {
  23.  >   int result=1, i;
  24.  > 
  25.  >   if(n>1) 
  26.  >     for(i=1;i<=n;i++)
  27.  >     {
  28.  >       result*=i;
  29.  >       while(result%10==0) result/=10;
  30.  >       result%=100;
  31.  >     }
  32.  >   return temp%10;
  33.  > }
  34.  > 
  35. Also this does not work as desired, even after changing the last "temp"
  36. to "result".  It fails when n=125 (for instance; actually the first
  37. failure is already at 25).  Can you explain why?
  38. And why 3 last digits will not suffice because that will fail at least
  39. at n=625 (first failure is actually at 375)?  Maintaining the last 4
  40. digits is good enough, but that will fail at 3125 ;-).
  41. But wait, this suggests a method using a single temp digit:
  42.  
  43. int fact_lsd(int n)
  44. {
  45.    int r = 1, i, i1;
  46.    if(n > 1)
  47.       for(i = 1, i1 = 1; i <= n; i++, i1 = i)
  48.       {
  49.          /* cast out those disturbing fives. */
  50.          while(i1 % 5 == 0)
  51.          {
  52.             i1 /= 5;
  53.             /* multiply by 5 and divide by 10 */
  54.         r >>= 1;
  55.         /* but the result must be even (there are more factors 2 than 5) */
  56.         if(r & 1) r += 5;
  57.          }
  58.          r = (r * i1) % 10;
  59.       }
  60.    }
  61.    return r;
  62. }
  63. -- 
  64. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  65. home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  66.